/**
 * 项目名称: Topic_623.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月30日08时13分52秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<TreeNode*>init;
    vector<vector<TreeNode*>>vn;

    void pre(TreeNode* root,int study){
        if(!root)return;
        if(vn.size()<=study)vn.push_back(init);
        vn[study].push_back(root);
        int tar = study+1;
        pre(root->left,tar);
        pre(root->right,tar);
    }
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(!root)return nullptr;
        if(depth==1){
            TreeNode* p = new TreeNode(val);
            if(!root)return p;
            else {
                p->left = root;
            }
            return p;
        }
        vn.push_back(init);
        pre(root,0);

        if(depth == vn.size()+1){
            for(int i = 0;i<vn[vn.size()-1].size();i++){
                TreeNode * p1=new TreeNode(val);
                TreeNode * p2 = new TreeNode(val);
                vn[vn.size()-1][i]->left = p1;
                vn[vn.size()-1][i]->right=p2;
            }
            return root;
        }

        for(int i = 0;i<vn[depth-2].size();i++){
            if(vn[depth-2][i]->left){
                TreeNode* p = new TreeNode(val);
                TreeNode* op = vn[depth-2][i]->left;
                vn[depth-2][i]->left = p;
                p->left = op;
            }
            else{
                TreeNode* p = new TreeNode(val);
                vn[depth-2][i]->left = p;
            }
            if(vn[depth-2][i]->right){
                TreeNode* p = new TreeNode(val);
                TreeNode* op = vn[depth-2][i]->right;
                vn[depth-2][i]->right = p;
                p->right = op;
            }
            else{
                TreeNode* p = new TreeNode(val);
                vn[depth-2][i]->right = p;
            }
        }
        return root;
    }
};
